20240622 2663 - Hard - Greedy

2663. Lexicographically Smallest Beautiful String

• 回文串的重要性质：因为长的回文串的中间都是 23 长度的回文串，如果不存在 23 的回文串，则不存在更长的回文串
  • 比如长度为 4 的回文串中间有长度为 2 的回文串
  • 长度为 5 的回文串中间有长度为 3 的回文串
• 把 s 视作一个 k 进制数，把字母 a 视作 0，字母 b 视作 1，依此类推。
• 从后往前加递增字母
  • 如果 i 和 i+1 或 i+2 形成回文串，则当前数字加 1
  • 如果超过 k 则进位

class Solution:
    def smallestBeautifulString(self, s: str, k: int) -> str:
        a = ord('a')
        k += a
        s = list(map(ord, s))
        n = len(s)
        i = n - 1  # 从最后一个字母开始
        s[i] += 1  # 先加一
        while i < n:
            if s[i] == k:  # 需要进位
                if i == 0:  # 无法进位
                    return ""
                # 进位
                s[i] = a
                i -= 1
                s[i] += 1
            elif i and s[i] == s[i - 1] or i > 1 and s[i] == s[i - 2]:
                s[i] += 1  # 如果 s[i] 和左侧的字符形成回文串，就继续增加 s[i]
            else:
                i += 1  # 反过来检查后面是否有回文串
        return ''.join(map(chr, s))